package com.shr.leetcode;

/**
 * leetcode: 477
 * @author sevn
 *
 */
public class TotalHammingDistance {
	
    public static int totalHammingDistance(int[] nums) {
    	
    	/**
    	 *  一次判断数组中所有元素的一位，从低到高。如果某位上，为0的元素有m个，为1的元素有n个，
    	 *  则该位会产生的Hamming distance为m*n个。所有位的依次相加。
    	 */
    	int sum = 0 ;
    	int[][] status = new int[32][2];
    	for(int i = 0;i<nums.length;i++){
    		int num = nums[i];
    		for(int j = 0;j<status.length;j++){
    			int bitStatus = num & 1;
    			if(bitStatus == 0)
    				status[j][0]++ ;
    			else status[j][1]++;
    			num >>= 1 ;
    		}
    	}
    	for(int j = 0;j<status.length;j++){
    		sum += status[j][0] * status[j][1] ;
    	}
    	
    	return sum ;
    	/**
    	 * 超时
    	 */
//        int sum = 0;
//        for(int i = 0;i < nums.length-1;i++){
//        	int aNum = nums[i] ;
//        	for(int j = i+1;j<nums.length;j++){
//        		int anotherNum = nums[j] ;
//        		int tNum = aNum ^ anotherNum ;
//        		String binaryStr = Integer.toBinaryString(tNum);
//        		for(int k = 0;k<binaryStr.length();k++){
//        			if(binaryStr.charAt(k) == '1')
//        				sum ++ ;
//        		}
//        			
//        	}
//        }
//        
//        return sum ;
    }
	
	public static void main(String[] args) {
		int[] nums = {4, 14, 2};
		System.out.println(totalHammingDistance(nums));
	}
}
